package middle;

public class Solution_337 {

    public static void main(String[] args) {
        Solution_337 model = new Solution_337();
//        TreeNode root = new TreeNode(3);
//        root.left = new TreeNode(2);
//        root.left.right = new TreeNode(3);
//        root.right = new TreeNode(3);
//        root.right.right = new TreeNode(1);

//        TreeNode root = new TreeNode(3);
//        root.left = new TreeNode(4);
//        root.left.left = new TreeNode(1);
//        root.left.right = new TreeNode(3);
//        root.right = new TreeNode(5);
//        root.right.right = new TreeNode(1);

        TreeNode root = new TreeNode(79);
        root.left = new TreeNode(99);
        root.right = new TreeNode(77);
        root.right.right = new TreeNode(69);
        root.right.right.right = new TreeNode(60);
        root.right.right.right.left = new TreeNode(53);
        root.right.right.right.left.left = new TreeNode(73);
        root.right.right.right.left.right = new TreeNode(11);
        root.right.right.right.left.right.right = new TreeNode(62);
        root.right.right.right.left.right.right.left = new TreeNode(27);
        root.right.right.right.left.right.right.right = new TreeNode(62);
        root.right.right.right.left.right.right.right.left = new TreeNode(98);
        root.right.right.right.left.right.right.right.right = new TreeNode(50);
        root.right.right.right.left.right.right.right.right.left = new TreeNode(90);
        root.right.right.right.left.right.right.right.right.right = new TreeNode(48);
        System.out.println(model.rob(root));
        System.out.println();
    }

    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        } else if (root.left == null && root.right == null) {
            return root.val;
        } else if (root.left == null) {
            int num_1 = rob(root.right);
            int num_2 = root.val;
            if (root.right.left != null) {
                num_2 += root.right.left.val;
            }
            if (root.right.right != null) {
                num_2 += root.right.right.val;
            }
            int val = Math.max(num_1, num_2);
            root.val = val;
            return val;
        } else if (root.right == null) {
            int num_1 = rob(root.left);
            int num_2 = root.val;
            if (root.left.left != null) {
                num_2 += root.left.left.val;
            }
            if (root.left.right != null) {
                num_2 += root.left.right.val;
            }
            int val = Math.max(num_1, num_2);
            root.val = val;
            return val;
        }
        int leftMaxValue = rob(root.left);
        int rightMaxValue = rob(root.right);

        int num_1 = leftMaxValue + rightMaxValue;
        int num_2 = root.val;
        if (root.left != null) {
            if (root.left.left != null) {
                num_2 += root.left.left.val;
            }
            if (root.left.right != null) {
                num_2 += root.left.right.val;
            }
        }
        if (root.right != null) {
            if (root.right.left != null) {
                num_2 += root.right.left.val;
            }
            if (root.right.right != null) {
                num_2 += root.right.right.val;
            }
        }
        int max = Math.max(num_1, num_2);
        root.val = max;
        return max;
    }

    static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
